package org.lintcode_Pattern;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: qingle
 * @Date: 2024/8/20-23:01
 * @Description:
 * 使用条件
 * • 需要查询包含某个前缀的单词/字符串是否存在
 * • 字符矩阵中找单词的问题
 * 复杂度
 * • 时间复杂度 O(L) 增删查改
 * • 空间复杂度 O(N * L) N 是单词数，L 是单词长度
 * 炼码例题
 * • LintCode 1221. 连接词
 * • LintCode 1624. 最大距离
 * • LintCode 1090. 映射配对之和
 * @version: 1.0
 */
public class A11字典树 {
	class TrieNode {
		// 子节点
		public Map<Character, TrieNode> children;
		// 根节点到该节点是否是一个单词
		public boolean isWord;
		// 根节点到该节点的单词是什么（可选）
		public String word;

		public TrieNode() {
			children = new HashMap<>();
			isWord = false;
			word = null;
		}
	}

	public class Trie {
		private final TrieNode root;

		public Trie() {
			root = new TrieNode();
		}

		public TrieNode getRoot() {
			return root;
		}

		// 插入单词
		public void insert(String word) {
			TrieNode node = root;
			for (int i = 0; i < word.length(); i++) {
				char letter = word.charAt(i);
				if (!node.children.containsKey(letter)) {
					node.children.put(letter, new TrieNode());
				}
				node = node.children.get(letter);
			}
			node.isWord = true;
			node.word = word;
		}

		// 判断单词 word 是不是在字典树中
		public boolean hasWord(String word) {
			int L = word.length();
			TrieNode node = root;
			for (int i = 0; i < L; i++) {
				char letter = word.charAt(i);
				if (!node.children.containsKey(letter)) {
					return false;
				}
				node = node.children.get(letter);
			}
			return node.isWord;
		}

		// 判断前缀 prefix 是不是在字典树中
		public boolean hasPrefix(String prefix) {
			int L = prefix.length();
			TrieNode node = root;
			for (int i = 0; i < L; i++) {
				char letter = prefix.charAt(i);
				if (!node.children.containsKey(letter)) {
					return false;
				}
				node = node.children.get(letter);
			}
			return true;
		}

		// 其他字典树操作，如搜索、删除等...
	}
}
